112. Path Sum

题目描述：

給定一個二元樹的根節點 root 和一個整數 targetSum，判斷該樹中是否存在從根節點到葉子節點的路徑，使得這條路徑上所有節點的值相加等於目標和 targetSum。

葉子節點 是指沒有子節點的節點。

Example :

• Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
• Output: true

解題思路:
這道題目是關於二元樹的實作題，有兩種常見的解法：遞迴法和迭代法。我們先介紹比較直觀的遞迴法來解決這個問題。

遞迴法的思路是從根節點開始，沿著樹向下遞迴。在遞迴過程中，每次將 targetSum 減去當前節點的值，然後將剩餘的 targetSum 傳遞給下一層的子節點。當抵達葉子節點時，檢查剩餘的 targetSum 是否正好等於該葉子節點的值。如果相等，則說明存在這樣的一條路徑，使得所有節點的值相加等於 targetSum。

var hasPathSum = function(root, targetSum) {
    if (!root) return false;

    if (!root.left && !root.right) return root.val === targetSum;
    
    const remainingSum = targetSum - root.val;
    return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);
};

時間複雜度：O(n)，其中 n 是二元樹中的節點數。每個節點都會被訪問一次。
空間複雜度：O(h)，其中 h 是樹的高度。遞迴call stack的深度取決於樹的高度。

迭代法的思路與遞迴法相似，不過是將遞迴過程轉換為使用 stack 來進行操作。具體來說，使用 stack 來儲存節點以及到達該節點時targetSum 減去節點值後所剩餘的targetSum。當抵達葉子節點時，檢查這個剩餘的 targetSum 是否為 0，如果相等，則表示存在這樣的一條路徑。這個過程會不斷重複，直到 stack 為空。如果最終 stack 為空時仍然沒有找到滿足條件的路徑，則說明不存在符合條件的結果。

var hasPathSum = function(root, targetSum) {
    if (!root) return false;

    const stack = [[root, targetSum - root.val]];

    while (stack.length > 0) {
        const [node, currSum] = stack.pop();

        if (!node.left && !node.right && currSum === 0) {
            return true;
        }

        if (node.right) {
            stack.push([node.right, currSum - node.right.val]);
        }

        if (node.left) {
            stack.push([node.left, currSum - node.left.val]);
        }
    }

    return false;
};

時間複雜度：O(n)，其中 n 是二元樹中的節點數。每個節點都會被訪問一次。
空間複雜度：O(h)，其中 h 是樹的高度。在最壞情況下，stack 中儲存的節點數與樹的高度成正比。

總結:
這道題目可以歸類為「recursion」和「stack」這兩個分類。遞迴法和迭代法的優缺點已在 LeetCode 的 100. Same Tree 中有詳細說明，建議有興趣的讀者可以參考該題目來深入理解這兩種方法的差異與應用。

透過對二元樹相關題目的練習，不僅能提升你對遞迴、迭代這些基本編程技巧的掌握，還能幫助你熟悉如何在不同場景中靈活運用堆疊（stack）和佇列（queue）。這些技巧在解決各類樹結構問題時尤為重要，也為你應對更複雜的編程挑戰打下堅實基礎。

此外，隨著練習的深入，你會發現這些技術不僅僅適用於樹結構，還可以廣泛應用於圖、連結串列等其他數據結構的問題中。多多練習，將有助於你在各種算法挑戰中游刃有餘。